package com.lihepeng.leecode.dp;

import java.util.Arrays;

/**
 *  给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
 *
 * 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
 *
 * 你可以认为每种硬币的数量是无限的。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/coin-change
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution322 {
    int [] memo;
    public int coinChange(int[] coins, int amount) {
        memo = new int[amount+1];
        Arrays.fill(memo,-666);
        return dp(coins,amount);
    }

    /**
     * 等同于子问题 dp[coins,amount-coin]+1
     * @param coins
     * @param amount
     * @return
     */
    public int dp(int[] coins, int amount) {
        if (amount ==0) {
            return 0;
        }
        if (amount <0) {
            return -1;
        }
        if (memo[amount] !=-666) {
            return memo[amount];
        }
        int res = Integer.MAX_VALUE;
        for (int coin : coins) {
            int sub_question = dp(coins,amount-coin);
            if (sub_question == -1) {
                // 无解
                continue;
            }
            // 在子问题中找到最优解
            res = Math.min(res,sub_question+1);

        }

        // 把计算结果存入备忘录
        memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;
        return res == Integer.MAX_VALUE?-1:res;
    }

}
